package leetcode.code1617;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {
	public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {
		List<List<Integer>> nexts = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			nexts.add(new ArrayList<>());
		}
		for (int[] edge : edges) {
			int x = edge[0] - 1, y = edge[1] - 1;
			nexts.get(x).add(y);
			nexts.get(y).add(x);
		}
		int[] ans = new int[n - 1];
		for (int i = 1; i < 1 << n; i++) {
			int mask = i, root = i & -i;
			if (Integer.bitCount(mask) == 1)
				continue;
			int[] j = dfs1(31 - Integer.numberOfLeadingZeros(root), mask ^ root, nexts);// j[0] 经过的点集，j[1]最远点距离，j[2]
																						// 最远点节点
			if (j[0] != mask) {
				continue;
			}
			int[] dist = dfs1(j[2], mask ^ (1 << (j[2])), nexts);
			ans[dist[1] - 1]++;
		}
		return ans;
	}

	private int[] dfs1(int root, int mask, List<List<Integer>> nexts) {
		int ans1 = 1 << root, ans2 = 0, ans3 = root;
		for (int next : nexts.get(root)) {
			if ((mask & (1 << next)) != 0) {
				int[] cur = dfs1(next, mask ^ (1 << next), nexts);
				ans1 |= cur[0];
				int dist = cur[1] + 1;
				if (dist > ans2) {
					ans2 = dist;
					ans3 = cur[2];
				}
			}
		}
		return new int[] { ans1, ans2, ans3 };
	}

	@Override
	public void debug4() {
		H.print(this.countSubgraphsForEachDiameter(4, H.str2array1("[[1,2],[2,3],[2,4]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int root = 32 - Integer.numberOfLeadingZeros(0b11001100) - 1;
		System.out.println(Integer.toBinaryString(Integer.numberOfLeadingZeros(0b11001100)));
		System.out.println(Integer.toBinaryString(root));
	}

}
